// https://leetcode.cn/problems/top-k-frequent-words/

// 题干：给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
//      返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

// 示例：输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
//      输出: ["i", "love"]

// 碎语：利用堆和容器来解决这个问题，字典序的要求也要考虑
//       先用一个哈希表统计一下每一个单词的频次

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    typedef pair<string, int> PSI;

    struct cmp
    {
        bool operator()(const PSI& a, const PSI& b){
            if (a.second == b.second){
                return a.first < b.first;
            } // 频次相同，字典序按照大根堆的方式排列
            return a.second > b.second;
        }
    };

public:
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        // 1.预处理一下原始的字符串数组
        unordered_map<string, int> hash;
        for (const auto& str : words) hash[str]++;

        // 2.创建一个大小为K的堆 (频次：小根堆 字典序（频次相同的时候):大根堆）
        priority_queue<PSI, vector<PSI>, cmp> heap;

        // 3.循环 （让元素依次进堆，然后再判断）
        for (const auto& psi : hash){
            heap.push(psi);
            if (heap.size() > k) heap.pop();
        }

        // 4.提取结果
        vector<string> ret(k);
        for (int i = k - 1 ; i >= 0 ; i--){
            ret[i] = heap.top().first;
            heap.pop();
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};

    vector<string> index = sol.topKFrequent(words, 2);
    for (const auto& str : index){
        cout << str << " ";
    }
    cout << endl;
    
    return 0;
}